The present invention relates to apparatus for decoding a variable length code represented by a code tree.
A known variable length code represented by a code tree is, for example, the modified Huffman code. This is obtained by encoding a black and white run length of scanned picture by the Huffman encoding scheme, as described, for example, in R. Hunter et al, "International Digital Facsimile Coding Standards", Proceeding of the IEEE, July 1980, Vol. 68, No. 7, pp. 854-867, Chapter IV entilted "One-Dimensional Coding Scheme". A conventional decoding method for this modified Huffman Code is to select one of two branches at each node in a code tree depending on whether "1" or "0" is detected for individual bits of the input code, ultimately arriving at a terminal node indicating a decoded result. To perform this, it is necessary to access a decoding table memory for each bit of the input data and to decide, for each memory output, whether the terminal node is reached or not. This increases the number of steps for processing, including the time-consuming steps of memory access and decision processing, resulting in the overall processing time becoming relatively long. Therefore, the abovementioned prior art decoding method is disadvantageous in that it can be realized only by the use of a high-speed microprocessor or wired logic circuit.
Though not intended for the code of facsimile, a method of increasing the decoding rate for the Huffman code is described in Frank U.S. Pat. No. 3,883,847 issued May 13, 1975, for "Uniform Decoding of Minimum-Redundancy Codes". With the decoding method of this patent, data of a predetermined number of bits is entered from an input code train to access a primary decoding table memory to read it out and, in the case where decoding is not completed by the readout, an address of a secondary decoding table memory to be accessed next is determined using the read out data and then the secondary decoding table memory is accessed by an input data of a plurality of bits entered next, thus obtaining a decoded result. This method raises the decoding rate but employs two decoding table memories, and hence has the defect that the overall storage capacity must be large.
It is an object of the present invention to provide decoding apparatus which is capable of high-speed decoding of a variable length code represented by a code tree without involving the bit-by-bit decoding operation and is small in the storage capacity of the decoding table memory used.